#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_set>
#include<unordered_map>
using namespace std;

int takeAttendance(vector<int>& records) {
    if (records.size() == 1)
    {
        if (records[0] == 1)
            return 0;
        else
            return 1;
    }
    int n = records.size();
    int left = 0;
    int right = records.size() - 1;
    while (left < right)
    {
        int mid = (right - left) / 2 + left;
        if (records[mid] > mid)
        {
            right = mid;
        }
        else
        {
            left = mid;
        }
        if (right == left + 1&&mid==left)
        {
            if (records[mid] == mid)
            {
                if (records[right] == right) return n;
                else return mid + 1;
            }
            else {
                return mid;
            }
        }
    }
    return 0;
}

int main()
{

    vector<int> nums = { 1,2,3 };
    vector<int> nums1 = { 1,1 };
    vector<int> nums2 = { 5,6,7,8,9 };
    vector<int> nums3 = { 8828,9581,49,9818,9974,9869,9991,10000,10000,10000,9999,9993,9904,8819,1231,6309 };
    vector<string>vs = { "fooo","barr","wing","ding","wing" };
    string s = "ADOBECODEBANC";
    string t = "ABC";
    takeAttendance(nums);

}